<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
  
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">

  
  <link href="../css/style.css" rel="stylesheet" type="text/css">

</head>
<body>
<h1>4.19. Рекурсивные процедуры</h1>
<p class="article">
В программировании рекурсивной называется процедура, которая прямо или косвенно вызывает саму себя. В этой статье мы рассмотрим классический пример рекурсии — вычисление факториала.
Что такое факториал? Это математическая функция, определённая для целых неотрицательных чисел. Обозначается восклицательным знаком (n! — факториал числа n). Факториал натурального числа равен произведению всех натуральных чисел до него. Факториал нуля равен 1.
</p>
<p class="article">
У факториала есть такое свойство: для натурального числа он равен произведению этого числа на факториал предыдущего натурального числа. Иными словами, факториал может быть определен формулой:
</p>
<div class="image">
	<img src="../img/14.19_1.png" />
</div>
<p class="article">
Наша задача — создать процедуру, которая будет возвращать 1, если параметр равен 0, иначе уменьшать его на 1 и вызывать саму себя!
Поскольку факториал определён для неотрицательных чисел, параметр процедуры и возвращаемое значение будут 16-битными целыми без знака. Параметр будет передаваться через стек, а результат возвращаться в регистре AX. Вот что у меня получилось:
</p>
<pre class="code">
; Рекурсивная процедура вычисления факториала
; вход: CX - число без знака
; выход: AX - результат
factorial:
    push bp                 ;Сохранение BP
    mov bp,sp               ;BP=SP
    mov ax,[bp+4]           ;AX=параметр
    test ax,ax              ;Проверка AX
    jz f_ret1               ;Если 0, вернуть 1
    dec ax                  ;Декремент AX
    push ax                 ;Помещение параметра в стек
    call factorial          ;Вызов процедуры для предыдущего числа
    mul word[bp+4]          ;Умножение результата на параметр процедуры
    jmp f_ret               ;Переход к возврату из процедуры
f_ret1:
    inc ax
f_ret:
    pop bp                  ;Восстановление BP
    ret 2                   ;Возврат из процедуры
</pre>
<p class="article">
Факториал — очень быстро возрастающая функция, поэтому мы не сможем этой процедурой вычислять его для чисел больше 8 (результат просто не влезет в 16 бит). Если вам нужно серьёзно вычислять факториал — используйте числа с плавающей точкой (хотя результат будет не совсем точным) или многобайтные целые (потребуется хитрая процедура умножения).
</p>
<h2>Недостатки рекурсии</h2>
<p class="article">
Основной недостаток рекурсии — это большое использование памяти в стеке. Рекурсия здорово ест ресурсы! При каждом вызове процедуры в стеке сохраняется адрес возврата, используемые регистры, параметры процедуры, а также может выделяться место для локальных переменных. Кроме того, на работу со стеком тратится дополнительное время, что может сделать рекурсию медленной.
К счастью, во многих случаях можно заменить рекурсию циклом. Старайтесь делать это везде, где возможно! Тот же самый факториал лучше вычислять в цикле. Сравните следующий код с рекурсивным вариантом:
</p>
<pre class="code">
; Процедура вычисления факториала в цикле
; вход: CX - число без знака
; выход: AX - результат
factorial_loop:
    push bp                 ;Сохранение BP
    mov bp,sp               ;BP=SP
    push cx                 ;Сохранение CX
    mov cx,[bp+4]           ;CX=параметр
    xor ax,ax               ;AX=0
    inc ax                  ;AX=1
    jcxz f_ret              ;Если CX=0, выход из процедуры
f_lp:
    mul cx                  ;Умножение
    loop f_lp               ;Команда цикла
f_ret:
    pop cx                  ;Восстановление CX
    pop bp                  ;Восстановление BP
    ret 2                   ;Возврат из процедуры
</pre>
</body>
</html>
